# leetcode: Anagrams | LeetCode OJ
# lintcode: (171) Anagrams
# Given an array of strings, return all groups of strings that are anagrams.

# Example
# Given ["lint", "intl", "inlt", "code"], return ["lint", "inlt", "intl"].

# Given ["ab", "ba", "cd", "dc", "e"], return ["ab", "ba", "cd", "dc"].
# Note
# All inputs will be in lower-case
from collections import Counter
def isAnagrams(s1,s2):
	return Counter(s1) == Counter(s2) 

def getAnagrams(l):
	if(len(l)<=1):
		return l
	st = set()
	for i in range(0,len(l)):
		for j in range(i+1,len(l)):
			if isAnagrams(l[i],l[j]):
				st.add(l[i])
				st.add(l[j])
			pass
	return st
print('["lint", "intl", "inlt", "code"]-------------------- \n')
l = ["lint", "intl", "inlt", "code"]
print(getAnagrams(l))

print('["ab", "ba", "cd", "dc", "e"]-------------------- \n')
l = ["ab", "ba", "cd", "dc", "e"]
print(getAnagrams(l))


# 复杂度分析
# 方法isAnagrams最坏的时间复杂度为 O(2L), 
# 其中 L 为字符串长度。双重for循环时间复杂度近似为 1/2O(n^2), 
# n 为给定字符串数组数目。
# 总的时间复杂度近似为 O(n^2 L)
# 使用了Vector String "visited"，空间复杂度可认为是 O(n).